1. Industrial Field of Utilization
The present invention relates to a pattern recording and transmitting apparatus using vector quantization coding for transmitting and recording, by replacing input patterns with index information of similar patterns, and more particularly to a vector quantization coding apparatus for transmitting and accumulating images by a small code quantity, and a decoding apparatus.
2. Related Art
Vector quantization is a technology for coding the pattern to be transmitted by high efficiency, by replacing the pattern information with representative vectors contained in a code book, and transmitting by coding the index. Already in the field of picture transmission, as disclosed by Murakami in "Image high efficiency coding by vector quantization," in Technical Report of Electronic Information Communication Society, IT85-61 (December 1985), the prototypes of vector quantization coding apparatus and decoding apparatus for television conferencing on the basis of this technology have been developed. As one of the problems of coding apparatus and decoding apparatus on the basis of vector quantization, it has been hitherto indicated that the performance largely depends on the design of representative vectors contained in the code book. To solve this problem, Linde et al. developed an algorithm called LBG after the initials of the researchers (Y. Linde, A. Buzo, and R. B. Gray: "An Algorithm for Vector Quantizer Design," IEEE Transaction on Communication, Vol. COM-28, No. 1, pp. 84-95, January 1980). In the LBG algorithm, the prior obtained learning system is used as the index, and starting from a proper initial code book, the dividing condition and representative condition are repeatedly applied in the learning system. In the meaning as, for example, least square error for the learning system, a semi-optimal representative vector can be obtained.
In the vector quantizer using the code book obtained by this algorithm, a favorable performance is obtained when the input pattern has the same statistic nature as the learning system used in design, but when the statistic nature is different, satisfactory coding characteristic cannot be obtained. It is hence attempted to update the code book so as to be applicable to an input system having a different statistical nature.
As the conventional vector quantization coding apparatus and decoding apparatus having such measures, the vector quantization coding transmission apparatus disclosed in the Japanese Laid-open Patent No. 2-145078 is known. This is called the first prior art. For dynamic learning of the code book corresponding to changes of the input system, in the first prior art, if there is an input vector producing a large error, the representative vectors in the code book are selectively rewritten. This is explained in FIG. 7.
In a code book 702 suppose a code book composed of N representative vectors is stored. Herein, y.sub.1, y.sub.2, . . . , y.sub.N are K-dimensional vectors. A vector quantization coding unit 701 receives a k-dimensional input vector x, and sends out index(x) expressed in formula 1 below as an index in FIG. 7. ##EQU1##
That is, the index of representative vector minimum in square error is provided. At the same time, the least square error at this time is dist(x) shown in formula 2. In FIG. 7 dist(x) is indicated as dist. ##EQU2##
A coding control unit 703 holds the selection frequency of representative vectors up to the present. The action differs with the value of dist(x). When dist(x) is smaller than a specific threshold Td, the selection frequency of index(x) is increased by 1, and the process distinguishing code for not updating the representative vector and the transmission index of representative vector are sent to a decoding control unit 704. When dist(x) is larger than the specific threshold Td, the index of minimum selection frequency up to the present (IDL in FIG. 7), the process distinguishing code for updating the representative vector, and the input vector x are transmitted. Consequently, the representative vector of the index of the minimum selection frequency of the code book 702 is erased, and instead the representative vector having the input vector x as selection frequency 1 is obtained (y.sub.n in the diagram).
In the decoding control unit 704, when the process distinguishing code indicates that the representative vector is not updated, index(x) is sent into a vector quantization decoding unit 705, and the vector quantization decoding unit 705 reads out the representative vector y.sub.m (m=index(x)) with its index(x) as the index, from a code book 706, and returns it to the decoding control unit 704. In the decoding control unit 704, it is outputted as x' in FIG. 7.
When the process distinguishing code to the decoding control unit 704 shows that the representative vector is updated, the code book is rewritten the same as at the coding side. At this time, the output x' of the decoding control unit 704 is the same as vector x. Sequentially, thus, vectors producing large errors are entered, the code books at the coding side and decoding side are matched, and the representative vectors of small selection frequency are rewritten, and therefore if the statistic nature of the input vector system is changed, it is expected that the coding performance will not deteriorate significantly.
On the other hand, instead of transmitting images by using vector quantization coding alone, other technology is also known to utilize the vector quantization in generation of prediction image and transmit or record the difference image of the prediction image and input image by using transform coding. An apparatus using the technology corresponding to this is disclosed by Nuno Miguel Borges de Pinho Cruz de Vasconcelos in "Library-based Image Coding Using Vector Quantization of the Prediction Space," MIT Master Thesis, September, 1993. This is called the second prior art.
The constitution of the second prior art is shown in FIG. 8. In the original text, the term library is used, but it is the same as code book, and hence the expression is changed to code book in the diagram. In the second prior art, it is a feature that vector quantization is added to the inter-frame prediction portion of conventional motion compensation digital cosine transform coding. Hereinafter, the digital cosine transform and its inverse transform are abbreviated as DCT, IDCT, respectively. In the diagram, operations of subtractor 805, motion compensation unit 806, motion estimating unit 807, DCT operation unit 808, quantizing unit 809, inverse quantizing unit 810, IDCT operation unit 811, and multiplexer 812 are exactly same as operations of the image coding system (MPEG2) cited in ISO-IEC/JTC1/SC29/WG11, MPEG Test Model, MPEG93/457 (1993), and hence detailed descriptions are omitted.
When a changeover switch 804 acts to select the output of the motion compensating unit 806, the coding apparatus in FIG. 8 processes same as the MPEG2 coding apparatus. In MPEG2, the motion is predicted in order to enhance the coding efficiency, and correspondence to the decoding result of the preceding frame is obtained (motion compensation), and the difference of motion compensated images is operated by DCT in a block of 8.times.8 pixels, and hence the image is coded.
In the second prior art, in addition to this MPEG2 processing, vector quantization is performed on the array of pixel values for composing the DCT block as, 64-dimensional vector. In the vector quantizing unit 803, 64-dimensional representative vectors are stored, and the index of the representative vector with least distortion to the input vector is outputted. When the least distortion at this time is smaller than the prediction error obtained from the motion compensating unit 806, the switch 804 is connected to the vector quantizing unit 803, the representative vector is put into the subtractor 805, and the difference is vector-quantized.
At the same time, the index of the representative vector is outputted to the multiplexer 812. The multiplexer 812 multiplexes inputs, and produces the output of the coding apparatus. The representative vector is produced in a code book designing unit 801 by using the LBG algorithm for the input vector of the past several frames in every frame. In this prior art, it is necessary to update the code book in the vector quantizing unit 803 in every frame, the code book updating unit 802 updates the code book in one of the following methods.
Method 1. Selective updating of code book: When the quantizing error when the code book used in the previous frame is applied in the present frame without change is within a specific threshold, the code book is not updated, and when exceeding the threshold, the representative vector in the code book is transmitted to the decoding side to be updated. As a result, when the change of the input vector system is small, it is not necessary to transmit the code book updating information.
Method 2. Updating of code book by difference information: Between the code book of the preceding frame and the code book newly determined in the present frame, the representative vector is determined so that the difference vector may be a minimum norm, and the difference vector is transmitted together with the corresponding relation. As a result, the updating information is compressed.
In this way, while suppressing the increase of redundant coding quantity due to code book updating, the block patterns entered in the past are stored by code book updating in addition to the inter-frame prediction by motion compensation, and by reproducing by vector quantization, for example, even when a concealed region re-appears, a favorable picture quality is obtained.
The prior arts had, however, the following problems.
Problem (1) Updating of code book: In the first prior art, if the input vector system contained many independent vectors not forming a group (having "off" values), the representative vector is updated every time an independent vector is entered, and the updating information occupies much of the code quantity, and the coding efficiency is lowered. Or when an independent vector is directly used as a representative vector, the optimality of the code book may be spoiled. In the second prior art, since the LBG algorithm is applied in every frame for updating the code book, it is free from the problem of optimality related to the first prior art, but the quantity of processing is colossal. Or, even by using the code book updating technique of the second prior art, updating of the entire code book is necessary, and lowering of coding efficiency is inevitable.
Problem (2) Composition of the code book: The second prior art is a mixed system of using vector quantization in generation of predictive image and using DCT in predictive error coding. At this time, the code book is composed by using the input vectors obtained from the entire picture in the learning system. That is, the code book is designed for the block pattern of the entire image. Therefore, in generation of the predictive image by vector quantization, for example, in order to have an effective of background a prediction, a code book having many representative vectors is created, and it is necessary to search the representative vector with least distortion at the time of vector quantization. It requires processing of a very heavy design load.
Problem (3) Block distortion: In vector quantization and DCT in the second prior art, the processing unit is a block having an image divided into rectangular sections, and in a limited coding quantity, the quantizing error of DC component in each block is sensed as block boundary, which disturbs visually. As transform coding not to detect block boundary, for example, sub-band coding is proposed by J. W. Woods and S. D. O'Neil in "Subband Coding of Images," IEEE Transaction on Acoustics Speech and Signal Processing, Vol. ASSP-34, No. 5, pp. 1278-1288 (October 1988).
In sub-band coding, the image is divided into different frequency bands by filter scanning. In this sub-band coding, since the image frequency components are not closed in block unlike discrete cosine transform, and the quantizing error of low frequency components are not sensed as a block boundary to cause visual disturbance. In FIG. 8, when the DCT operating unit 808 is replaced by the processing unit for sub-band decomposition operation, and the IDCT operating unit 811 by the processing unit for sub-band composition, sub-band coding is realized. However, when the DCT operating unit 808 is used as the processing unit for sub-band decomposition operation, since the predictive image coming in from the changeover switch 804 is a block unit, if different patterns are predicted in adjacent blocks, discontinuity occurs in the block boundary portion of the predictive image, and it must be coded in sub-band. In DCT coding, since the transform processing is closed within the block, discontinuity occurring in the block boundary of predictive image does not matter, but in sub-band coding, since the processing is not closed in block, the coding efficiency is lowered.